The compaction of data while it is being transmitted or held in long-term storage may be accomplished by variable-length coding. In this type of coding scheme, bit strings of fixed length are encoded into bit strings of variable-length, with the more frequently occurring bit strings or words being represented by the shorter-length code-words. If the assignment of variable-length code-words is judiciously done, their average length will be much even though many of the variable-length code words are much longer than the fixed-length code-words.
Huffman codes are minimum reduncancy variable-length codes that have the prefix-free properly, that is none of the code-words can form the beginning of a longer code-word. The construction of Huffman codes is described in an article by David A. Huffman entitled "A Method for the Construction of Minimum Redundancy Codes", in the proceedings of the I. R. E., Vol. 40, pp. 1098-1101, 1952. Huffman codes are usually preferred over other variable-length codes due to their straight forward construction and their optimum expected (average) code-word length.
Although variable-length coding is useful for reducing the facilities and time required for the transmission and storage of data, the compacted data cannot be utilized by a data processor computer in this form, and must be decoded back to a fixed-length code format. The processing costs involved in decoding Huffman codes have isolated them mostly to the theoretical domain. Decoding schemes have been proposed but they have deficiencies which make them unsuitable for general use. They either require too much time and/or memory for the decoding process or are strictly limited to particular probability distributions. Some require special hardware that is not ordinarily available in conventional data processors. Specifically, U.S. Pat. No. 4,396,906 discloses a method that can only be used on Huffman codes whose probability distributions produce degenerate decoding trees. Except for the degenerate case, the invention will not work without altering the optimum Huffman code. U.S. Pat. Nos. 3,701,111 and 3,717,851 present similar problems. No practical hardware means are presently available to decode general Huffman codes in a quick and efficient manner.
There is a great need at the present time for a convenient and practical way to decode variable-length codes with conventional hardware or data processors and without losing a significant amount of time in processing such data. If the decoding times can be decreased, it will greatly enhance the utility of Huffman or variable-length coding and make its savings available to designers of data processing and data communication systems.